#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		vector<int> arr(n);
		for(int i=0;i<n;i++)
			cin>>arr[i];
		sort(arr.begin(),arr.end());
		
		vector<int> dp(arr[n-1]+1);
		dp[0]=1;
		int ret=0;
		for(int i=0;i<n;i++)
		{
			if(!dp[arr[i]])ret++;
			for(int j=arr[i];j<=arr[n-1];j++)
			{
				dp[j]+=dp[j-arr[i]];
			}
		}
		cout<<ret<<endl;
	}
	return 0;
}
